import java.util.Objects;

/**
 * 1. 最长路径做多是最短路径的2倍
 * 2. 每个结点不是红色就是黑色
 * 3. 根节点是黑色的
 * 4. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】
 * 5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
 * 6. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)ss
 */

public class REDTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        COLOUR colour;
        public TreeNode(int val) {
            this.val = val;
            this.colour = COLOUR.RED;// 插入默认是红色的
        }
    }
    TreeNode root;
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(this.root == null) {
            root = node;
            root.colour = COLOUR.BREAK;
            return true;
        }
        // 不是第一次插入，按照二叉搜索树插入方式插入
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                // cur.val == val 表示当前节点已经存在了
                return false;
            }
        }
        // 当前cur 已经到达叶子节点了
        if(parent.val > val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        cur = node;
        node.parent = parent;

        // 当前已经成功插入了

        while(parent != null && parent.colour == COLOUR.RED) {
            TreeNode grandFather = parent.parent; // parent 为红色，那他一定有父节点 （根节点必须是黑色）
            if(parent == grandFather.left ) {
                TreeNode uncle = grandFather.right;
                if(uncle != null && uncle.colour == COLOUR.RED) {
                    // uncle 存在并且为红色
                    parent.colour = COLOUR.BREAK;
                    uncle.colour = COLOUR.BREAK;
                    cur = grandFather;
                    cur.colour = COLOUR.RED;
                    parent = cur.parent;
                    // 继续向上调整
                }else {
                    // 情况三
                    if(cur == parent.right) {
                        totateRight(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent = tmp;
                    }

                    // 情况二
                    // cur 不存在 或者 uncle 为黑色
                    totateLeft(grandFather);
                    grandFather.colour = COLOUR.RED;
                    parent.colour = COLOUR.BREAK;
                }
            }else {
                TreeNode uncle = grandFather.left;
                if(uncle != null && uncle.colour == COLOUR.RED) {
                    // uncle 存在并且为红色
                    parent.colour = COLOUR.BREAK;
                    uncle.colour = COLOUR.BREAK;
                    cur = grandFather;
                    cur.colour = COLOUR.RED;
                    parent = cur.parent;
                    // 继续向上调整
                }else {
                    // 情况三
                    if(cur == parent.left) {
                        totateRight(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent = tmp;
                    }

                    // 情况二
                    // cur 不存在 或者 uncle 为黑色
                    totateLeft(grandFather);
                    grandFather.colour = COLOUR.RED;
                    parent.colour = COLOUR.BREAK;
                }
            }
        }
        root.colour = COLOUR.BREAK;
        return true;
    }

    private void totateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if(subRL != null) {
            subRL.parent = parent;
        }
        TreeNode pParent = parent.parent;

        parent.parent = subR;
        if(parent == root) {
            // 表示当前是根节点了
            root = subR;
            subR.parent = null;
            return ;
        }else {
            // parent 有父节点 重新绑定父节点
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }

    private void totateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        subL.right = parent;
        parent.left = subLR;
        if(subLR != null) {
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        // 调整成功
        if(parent == root) {
            subL.parent = null;
            return;
        }else {
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                // pParent.right == parent
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }
    public boolean isREDTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.colour != COLOUR.BREAK) {
            System.out.println("违反了红黑树的性质：根节点为红色");
        }
        int blackNum = 0;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.colour == COLOUR.BREAK) {
                blackNum++;
            }
            cur = cur.left;
        }
        return checkRedColor(root) && checkBlackNum(root,0,blackNum);
    }

    private boolean checkBlackNum(TreeNode root, int pathBlackNum, int blackNum) {
        if(root == null) return true;
        if(root.colour == COLOUR.BREAK) {
            pathBlackNum++;
        }
        if(root.left == null && root.right == null) {
            if(pathBlackNum != blackNum) {
                System.out.println(root.val);
                System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的！");
                return false;
            }
        }

        return checkBlackNum(root.left,pathBlackNum,blackNum) && checkBlackNum(root.right,pathBlackNum,blackNum);
    }

    private boolean checkRedColor(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.colour == COLOUR.RED) {
            if(root.parent.colour != COLOUR.BREAK) {
                System.out.println("违反了红黑树的性质 ：存在两个连续的红色节点");
                return false;
            }
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }

    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

}
